using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace BigNumber
{
  public delegate StdBigNumber StdTwoNumbersFunction(StdBigNumber firstNumber,StdBigNumber secondNumber);

  [Serializable]
  public class StdBigNumber : IIntegerBigNumber, IConvertible, IComparable<StdBigNumber>
  {
    private List<byte> m_Number;
    private bool m_IsNegative;

    #region Helper Functions
    private byte CharToByte(char ch)
    {
      if (!Char.IsDigit(ch))
        throw new Exception("Trying to convert icorrect char to byte - " + ch);
      return byte.Parse(ch.ToString());
    }
    internal void RemoveLeadingZeros()
    {
      if (m_Number.Count <= 1) return;
      int i = m_Number.Count-1;
      while (i>0 && m_Number[i] == 0)
      {
        m_Number.RemoveAt(i);
        i--;
      }
    }
    internal void SetDigit(int index, byte digit)
    {
      m_Number[index] = digit;
    }
    /// <summary>
    /// Adds the most significant digit to the number
    /// </summary>
    /// <param name="digit">the digit to add</param>
    internal void AddDigit(byte digit)
    {
      m_Number.Add(digit);
    }

    /// <summary>
    /// Return the count most significant digits as a new positive StdBigNumber
    /// For example calling this function on 123456 with count = 3 will result in 123
    /// </summary>
    /// <param name="count">how many significany digits to cut</param>
    /// <returns>See summary. If count > than the length of the number only the length significant digits are returned</returns>
    private StdBigNumber CutSignificantDigits(int count)
    {
      Debug.Assert(count > 0);
      StdBigNumber result = new StdBigNumber(true);
      for (int i = m_Number.Count - 1; i >= 0 && count > 0; i--, count--)
      {
        result.m_Number.Insert(0,m_Number[i]);
      }
      return result;
    }

    /// <summary>
    /// Returns how many times number can be in current number must be smaller than byte times
    /// </summary>
    /// <param name="number"></param>
    /// <returns>this/number</returns>
    private byte SmallDivide(StdBigNumber number)
    {
      if (number.IsZero)
        throw new DivideByZeroException("Division by zero in StdBigNumber (SmallDivide)");
      //TODO : Need better algorithm here
      if (this < number) return 0;
      byte result = 1;
      StdBigNumber tempNumber = new StdBigNumber(number);
      while (tempNumber <= this)
      {
        tempNumber = tempNumber + number;
        result++;
      }
      return (byte)(result-1);
    }

    /// <summary>
    /// Returns a new StdBigNumber that is the result of this * second number
    /// </summary>
    /// <param name="secondNumber"></param>
    /// <returns></returns>
    private StdBigNumber SmallMultiply(byte secondNumber)
    {
      if (secondNumber == 0) return new StdBigNumber(false);
      StdBigNumber result = new StdBigNumber(true);
      int carry = 0;
      for (int i = 0; i < m_Number.Count; i++)
      {
        int newDigit = (m_Number[i] * secondNumber + carry);
        if (newDigit > 9)
        {
          carry = (newDigit / 10);
          newDigit = newDigit % 10;
        }
        else
        {
          carry = 0;
        }
        result.AddDigit((byte)newDigit);
      }
      if (carry > 0)
        result.AddDigit((byte)carry);
      return result;
    }

    /// <summary>
    /// WARNING! Does not generate a new number! Treats this as a positive number.
    /// Returns a the current StdBigNumber that is the result of this + second number
    /// </summary>
    /// <param name="secondNumber"></param>
    /// <returns></returns>
    private void SmallAdd(byte secondNumber)
    {
      if (secondNumber == 0) 
        return;
      m_Number[0] +=  secondNumber;
      for (int i = 0; i < m_Number.Count-1 && m_Number[i] > 9; i++) 
      {
        m_Number[i] -= 10;
        m_Number[i + 1]++;
      }
      int index = m_Number.Count-1;
      if (m_Number[index] > 9)
      {
        m_Number[index] -= 10;
        m_Number.Add(1);
      }
    }

    #region Simple Divisibility
    internal bool IsDivisibleByTwo
    {
      get
      {
        byte digit = m_Number[0];
        if (digit == 0 || digit == 2 || digit == 4 || digit == 6 || digit == 8)
          return true;
        return false;
      }
    }

    internal bool IsDivisibleByThree
    {
      get
      {
        StdBigNumber tempAdded = new StdBigNumber(false);
        StdBigNumber tempNotAdded = this;
        while (tempNotAdded.DigitCount > 1)
        {
          for (int i = 0; i < tempNotAdded.m_Number.Count; i++)
            tempAdded.SmallAdd(tempNotAdded.m_Number[i]);
          tempNotAdded = tempAdded;
          tempAdded = new StdBigNumber(false);
        }
        if (tempNotAdded.m_Number[0] == 3 || tempNotAdded.m_Number[0] == 6 || tempNotAdded.m_Number[0] == 9)
          return true;
        return false;
      }
    }

    internal bool IsDivisibleByFive
    {
      get
      {
        byte digit = m_Number[0];
        if (digit == 0 || digit == 5)
          return true;
        return false;
      }
    }

    internal bool IsDivisibleBySeven
    {
      get
      {
        StdBigNumber tempNumber = new StdBigNumber(this);
        while (tempNumber.m_Number.Count > 1)
        {
          int digit = tempNumber.m_Number[0];
          tempNumber.m_Number.RemoveAt(0);
          digit = digit * 2;
          StdBigNumber temp = new StdBigNumber(digit.ToString());
          tempNumber = tempNumber - temp;
          tempNumber.IsNegative = false;
        }
        return tempNumber.m_Number[0] == 7 || tempNumber.m_Number[0] == 0;
      }
    }

    internal bool IsDivisibleByEleven
    {
      get
      {
        StdBigNumber odd = new StdBigNumber(false);
        StdBigNumber even = new StdBigNumber(false);
        for (int i = 0; i < m_Number.Count; i++)
        {
          if ((i & 0x0001) == 1)
            odd.SmallAdd(m_Number[i]);
          else
            even.SmallAdd(m_Number[i]);
        }
        return odd == even;
      }
    }

    #endregion
    #endregion

    #region Constructors
      /// <summary>
      /// Creates a StdBigNumber with a value of 0 or without values
      /// </summary>
      /// <param name="createEmpty">if true then the StdNumber is created without digits and else its created with the digit 0</param>
    internal StdBigNumber(bool createEmpty)
    {
      m_Number = new List<byte>();
      IsNegative = false;
      if (!createEmpty)
        m_Number.Add(0);
    }

    public StdBigNumber()
      : this("0")
    {}

    public StdBigNumber(string number)
    {
      Initialize(number);
    }

    public StdBigNumber(int number):this(number.ToString())
    {}

    public StdBigNumber(Int64 number)
      : this(number.ToString())
    { }

    internal StdBigNumber(StdBigNumber number)
    {
      m_Number = new List<byte>(number.m_Number.Count);
      for (int i=0; i<number.m_Number.Count; i++)
        m_Number.Add(number.m_Number[i]);
      IsNegative = number.m_IsNegative;
    }

    #endregion

    #region Overrides
    public override string ToString()
    {
      StringBuilder sb = new StringBuilder();
      foreach (byte digit in m_Number)
      {
        sb.Insert(0,digit.ToString());
      }
      if (m_IsNegative && !IsZero)
        sb.Insert(0,'-');
      return sb.ToString();
    }
    public override int GetHashCode()
    {
      int result = 0;
      for (int i=0; i<m_Number.Count && i<4; i++)
      {
        result = result * 256 + m_Number[i];
      }
      return result;
    }
    public override bool Equals(object obj)
    {
      if (!(obj is StdBigNumber))
        throw new InvalidCastException("Trying to compare StdBigNumber to object "+obj.GetType().ToString());
      return (this as IComparable<StdBigNumber>).CompareTo((StdBigNumber)obj) == 0;
    }
    #endregion

    public void Initialize(string number)
    {
      if (number == null) number = "0";
      m_Number = new List<byte>();
      char[] numbers = number.ToCharArray();
      if (numbers.Length == 0)
      {
        throw new Exception("Initialize failed : Empty number passed");
      }
      if (numbers[0] == '-')
      {
        m_IsNegative = true;
        numbers[0] = '0';
      }
      foreach (char ch in numbers)
      {
        m_Number.Insert(0,(CharToByte(ch)));
      }
      RemoveLeadingZeros();
      if (IsZero)
        m_IsNegative = false;
    }

    public int GetDigit(int index)
    {
      if (index >= 0 && index < m_Number.Count)
        return m_Number[index];
      else
        throw new Exception("GetDigit failed : Index out of bounds " + index.ToString());
    }

    public void Negate()
    {
      if (IsZero)
        return;
      m_IsNegative = !m_IsNegative;
    }

    public void AddOne()
    {
      if (IsNegative)
      {
        m_Number[0]--;
        int i = 0;
        while (m_Number[i] < 0)
        {
          m_Number[i] = 9;
          i++;
          m_Number[i]--;
        }
        RemoveLeadingZeros();
        if (IsZero)
          IsNegative = false;
      }
      else
      {
        m_Number[0]++;
        int i = 0;
        while (i < m_Number.Count-1 && m_Number[i] == 10)
        {
          m_Number[i] = 0;
          i++;
          m_Number[i]++;
        }
        if (m_Number[i] == 10)
        {
          m_Number[i] = 0;
          m_Number.Add(1);
        }
      }
    }

    public void Shift(int n)
    {
      for (int i = 0; i < n; i++)
        m_Number.Insert(0,0);
    }

    public bool IsNegative
    {
      get { return m_IsNegative; }
      internal set 
      {
        if (IsZero) m_IsNegative = false;
        else m_IsNegative = value;
      }
    }

    public int DigitCount
    {
      get { return m_Number.Count; }
    }

    public bool IsZero
    {
      get 
      {
        if (m_Number.Count == 1 && m_Number[0] == 0)
          return true;
        return false;
      }
    }

    public bool IsOne
    {
      get 
      {
        if (m_Number.Count == 1 && m_Number[0] == 1)
          return true;
        return false;
      }
    }

    #region Public Functions and Properties
    public bool IsEven
    {
      get
      {
        if ((m_Number.Count > 0) && (m_Number[0] & 1) == 0)
          return true;
        return false;
      }
    }

    public bool IsOdd
    {
      get
      {
        return !IsEven;
      }
    }
    #endregion

    #region Private Static Functions

    private static StdBigNumber Add(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      #region Handle negative numbers
      if (firstNumber.IsNegative && secondNumber.IsNegative)
      {
        secondNumber.Negate();
        if (!object.ReferenceEquals(firstNumber,secondNumber)) //In case we activated the function on this
          firstNumber.Negate();
        StdBigNumber innerResult = Add(firstNumber,secondNumber);
        secondNumber.Negate();
        if (!object.ReferenceEquals(firstNumber, secondNumber))
          firstNumber.Negate();//In case we activated the function on this
        innerResult.Negate();
        return innerResult;
      }
      else
        if (firstNumber.IsNegative)
        {
          firstNumber.Negate();
          StdBigNumber innerResult = Subtract(secondNumber,firstNumber);
          firstNumber.Negate();
          return innerResult;
        }
        else
          if (secondNumber.IsNegative)
          {
            secondNumber.Negate();
            StdBigNumber innerResult = Subtract(firstNumber,secondNumber);
            secondNumber.Negate();
            return innerResult;
          }
      #endregion

      StdBigNumber result = new StdBigNumber(true);
      int minCount = Math.Min(secondNumber.DigitCount, firstNumber.DigitCount);
      int carry = 0;
      for (int i = 0; i < minCount; i++)
      {
        int temp = secondNumber.GetDigit(i) + carry + firstNumber.GetDigit(i);
        carry = temp / 10;
        int tempDigit = temp % 10;
        result.AddDigit(Convert.ToByte(tempDigit));
      }
      for (int i = minCount; i < secondNumber.DigitCount; i++)
      {
        int temp = secondNumber.GetDigit(i) + carry;
        carry = temp / 10;
        int tempDigit = temp % 10;
        result.AddDigit(Convert.ToByte(tempDigit));
      }
      for (int i = minCount; i < firstNumber.DigitCount; i++)
      {
        int temp = firstNumber.GetDigit(i) + carry;
        carry = temp / 10;
        int tempDigit = temp % 10;
        result.AddDigit(Convert.ToByte(tempDigit));
      }
      while (carry > 0)
      {
        int tempDigit = carry % 10;
        result.AddDigit(Convert.ToByte(carry));
        carry = carry / 10;
      }
      result.IsNegative = secondNumber.IsNegative;
      return result;
    }

    private static StdBigNumber Subtract(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {

      #region Handle Negative Numbers
      if (firstNumber.IsNegative || secondNumber.IsNegative)
      {
        secondNumber.Negate();
        StdBigNumber innerResult = Add(firstNumber,secondNumber);
        return innerResult;
      }
      #endregion
      // Make sure this >= otherNumer , if not subtract the other way and swap sign
      if (firstNumber.CompareTo(secondNumber) < 0)
      {                
        StdBigNumber innerResult = Subtract(secondNumber, firstNumber);
        innerResult.Negate();
        return innerResult;
      }

      StdBigNumber result = new StdBigNumber(true);
      int borrow = 0;
      int minCount = Math.Min(secondNumber.DigitCount, firstNumber.DigitCount);
      for (int i = 0; i < minCount; i++)
      {
        int temp = firstNumber.GetDigit(i) - borrow;
        int otherDigit = secondNumber.GetDigit(i);
        if (temp < otherDigit)
        {
          temp += 10;
          borrow = 1;
        }
        else
          borrow = 0;
        result.AddDigit(Convert.ToByte(temp - otherDigit));
      }
      for (int i = minCount; i < firstNumber.DigitCount; i++)
      {
        int temp = firstNumber.GetDigit(i) - borrow;
        if (temp < 0)
        {
          temp += 10;
          borrow = 1;
        }
        else
          borrow = 0;
        result.AddDigit(Convert.ToByte(temp));
      }
      //if (borrow != 0)
        Debug.Assert(borrow == 0); //This is because we made sure this number is greater or equal to otherNumber      
      result.RemoveLeadingZeros();
      return result;
    }

    private static StdBigNumber Multiply(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (firstNumber.IsZero || secondNumber.IsZero)
        return new StdBigNumber(false);
      if (firstNumber.DigitCount < secondNumber.DigitCount)
        return Multiply(secondNumber, firstNumber);
      StdBigNumber result = new StdBigNumber(false);
      for (int i = 0; i < secondNumber.DigitCount; i++)
      {
        StdBigNumber numberToAdd = new StdBigNumber(true);
        int otherDigit = secondNumber.GetDigit(i);
        if (otherDigit == 0)
          continue;
        numberToAdd=new StdBigNumber(firstNumber);
        if (otherDigit != 1)
        {
          int carry = 0;
          for (int j = 0; j < firstNumber.DigitCount; j++)
          {
            int newDigit = firstNumber.GetDigit(j) * otherDigit + carry;
            carry = newDigit / 10;
            newDigit = newDigit % 10;
            numberToAdd.SetDigit(j, Convert.ToByte(newDigit));
          }
          if (carry > 0)
            numberToAdd.m_Number.Add(Convert.ToByte(carry));
        }
        numberToAdd.Shift(i);
        result = Add(result, numberToAdd);
      }
      if (firstNumber.IsNegative != secondNumber.IsNegative)
        result.IsNegative = true;
      else
        result.IsNegative = false;
      return result;
    }

    private static StdBigNumber Divide(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      bool firstNegative = firstNumber.IsNegative;
      bool secondNegative = secondNumber.IsNegative;
      firstNumber.IsNegative = false;
      secondNumber.IsNegative = false;
      try
      {
        if (secondNumber.IsZero)
          throw new DivideByZeroException("Division by zero in StdBigNumber (Divide)");
        StdBigNumber result;
        if (secondNumber.IsOne)
        {
          result = new StdBigNumber(firstNumber);
          result.IsNegative = (firstNegative != secondNegative);
          return result;
        }
        int res = firstNumber.CompareTo(secondNumber);
        if (res < 0) return new StdBigNumber("0");
        if (res == 0)
        {
          result = new StdBigNumber("1");
          result.IsNegative = (firstNegative != secondNegative);
          return result;
        }
        result = new StdBigNumber(true);
        StdBigNumber tempNumber = firstNumber.CutSignificantDigits(secondNumber.DigitCount);
        int currentDigit = firstNumber.DigitCount - tempNumber.DigitCount;
        while (true)
        {
          byte digit = tempNumber.SmallDivide(secondNumber);
          result.m_Number.Insert(0, digit);
          tempNumber = tempNumber - secondNumber.SmallMultiply(digit); // not needed if small divide will return this as side effect
          currentDigit--;
          if (currentDigit < 0)
            break;
          tempNumber.m_Number.Insert(0, firstNumber.m_Number[currentDigit]);
          tempNumber.RemoveLeadingZeros();
        }
        result.IsNegative = (firstNegative != secondNegative);
        result.RemoveLeadingZeros();
        return result;
      }
      finally
      {
        firstNumber.m_IsNegative = firstNegative;
        secondNumber.m_IsNegative = secondNegative;
      }
    }

    private static StdBigNumber Modulus(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      bool firstNegative = firstNumber.IsNegative;
      bool secondNegative = secondNumber.IsNegative;
      firstNumber.IsNegative = false;
      secondNumber.IsNegative = false;
      try
      {
        if (secondNumber.IsZero)
          throw new DivideByZeroException("Division by zero in StdBigNumber (Modulus)");
        int res = firstNumber.CompareTo(secondNumber);
        if (res < 0)
        {
          StdBigNumber result = new StdBigNumber(firstNumber);
          result.IsNegative = firstNegative;
          return result;
        }
        if (res == 0) return new StdBigNumber(false);

        
        StdBigNumber tempNumber = firstNumber.CutSignificantDigits(secondNumber.DigitCount);
        int currentDigit = firstNumber.DigitCount - tempNumber.DigitCount;
        while (true)
        {
          byte digit = tempNumber.SmallDivide(secondNumber);
          tempNumber = tempNumber - secondNumber.SmallMultiply(digit); // not needed if small divide will return this as side effect
          currentDigit--;
          if (currentDigit < 0)
            break;
          tempNumber.m_Number.Insert(0, firstNumber.m_Number[currentDigit]);
          tempNumber.RemoveLeadingZeros();
        }
        tempNumber.IsNegative = firstNegative;
        return tempNumber;
      }
      finally
      {
        firstNumber.IsNegative = firstNegative;
        secondNumber.IsNegative = secondNegative;
      }
    }

    #endregion

    #region Public Static Functions

    public static StdBigNumber DigitProduct(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
      StdBigNumber result = new StdBigNumber(1);
      foreach (int x in number.m_Number)
        result *= x;
      return result;
    }

    public static StdBigNumber DigitSum(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
      StdBigNumber result = new StdBigNumber(0);
      foreach (int x in number.m_Number)
        result += x;
      return result;
    }

    public static bool IsPalindrome(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
        int i = 0;
        int j = number.m_Number.Count - 1;
        bool found = false;
        while (i < j && !found)
        {
          found = number.m_Number[i] != number.m_Number[j];
          i++;
          j--;
        }
        return !found;
    }

    public static StdBigNumber Reverse(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
      StdBigNumber result = new StdBigNumber(number);
      for (int i = 0; i < number.m_Number.Count; i++)
      {
        result.m_Number[number.m_Number.Count - 1 - i] = number.m_Number[i];
      }
      result.RemoveLeadingZeros();
      return result;
    }

    #endregion

    #region Operators

    #region Comparison Operators
    public static bool operator <(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");
      if (firstNumber.CompareTo(secondNumber) < 0)
        return true;
      return false;
    }

    public static bool operator >(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");
      if (firstNumber.CompareTo(secondNumber) > 0)
        return true;
      return false;
    }

    public static bool operator ==(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null) && ReferenceEquals(secondNumber ,null)) return true;
      if (ReferenceEquals(firstNumber,null)) return false;
      if (ReferenceEquals(secondNumber ,null)) return false;
      if (firstNumber.CompareTo(secondNumber) == 0)
        return true;
      return false;
    }

    public static bool operator !=(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null) && ReferenceEquals(secondNumber ,null)) return false;
      if (ReferenceEquals(firstNumber,null)) return true;
      if (ReferenceEquals(secondNumber ,null)) return true;
      if (firstNumber.CompareTo(secondNumber) != 0)
        return true;
      return false;
    }

    public static bool operator <=(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null) && ReferenceEquals(secondNumber ,null)) return true;
      if (ReferenceEquals(firstNumber,null)) return false;
      if (ReferenceEquals(secondNumber ,null)) return false;
      if (firstNumber.CompareTo(secondNumber) <= 0)
        return true;
      return false;
    }

    public static bool operator >=(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null) && ReferenceEquals(secondNumber ,null)) return true;
      if (ReferenceEquals(firstNumber,null)) return false;
      if (ReferenceEquals(secondNumber ,null)) return false;
      if (firstNumber.CompareTo(secondNumber) >= 0)
        return true;
      return false;
    }

    #endregion

    #region Math Operators

    public static StdBigNumber operator -(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
      StdBigNumber result = new StdBigNumber(number);
      result.Negate();
      return result;
    }

    public static StdBigNumber operator ++(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
      StdBigNumber result = new StdBigNumber(number);
      result.AddOne();
      return result;
    }

    public static StdBigNumber operator --(StdBigNumber number)
    {
      if (number == null) throw new ArgumentNullException("number");
      StdBigNumber result = new StdBigNumber(number);
      StdBigNumber mOne = -1;
      return result - 1;
    }

    public static StdBigNumber operator +(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");
      return Add(firstNumber, secondNumber);
    }

    public static StdBigNumber operator -(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");

      return Subtract(firstNumber, secondNumber);
    }

    public static StdBigNumber operator *(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");

      return Multiply(firstNumber, secondNumber);
    }

    public static StdBigNumber operator /(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");

      return Divide(firstNumber, secondNumber);
    }

    public static StdBigNumber operator %(StdBigNumber firstNumber, StdBigNumber secondNumber)
    {
      if (ReferenceEquals(firstNumber,null)) throw new ArgumentNullException("firstNumber");
      if (ReferenceEquals(secondNumber ,null)) throw new ArgumentNullException("secondNumber");

      return Modulus(firstNumber, secondNumber);
    }
    #endregion

    #region Implicit Convertions
    public static implicit operator int(StdBigNumber number)
    {
      checked
      {
        int result;
        if (Int32.TryParse(number.ToString(), out result))
          return result;
        else
          throw new Exception("Unable to convert StdBigNumber " + number.ToString() + " to integer");
      }
    }

    public static implicit operator StdBigNumber(int number)
    {
      return new StdBigNumber(number);
    }

    public static implicit operator StdBigNumber(string number)
    {
      return new StdBigNumber(number);
    }
    #endregion

    #endregion

    #region IConvertible Members

    TypeCode IConvertible.GetTypeCode()
    {
      return TypeCode.Object;
    }

    bool IConvertible.ToBoolean(IFormatProvider provider)
    {
      if (IsZero) return false;
      return true;
    }

    byte IConvertible.ToByte(IFormatProvider provider)
    {
      if (m_Number.Count == 1 && !IsNegative)
        return m_Number[0];
      throw new InvalidCastException(String.Format("Cannot convert {0} to byte because the values are incompatible", ToString()));
    }

    char IConvertible.ToChar(IFormatProvider provider)
    {
      if (m_Number.Count == 1 && !IsNegative)
        return Convert.ToChar(m_Number[0]);
      throw new InvalidCastException(String.Format("Cannot convert {0} to char because the values are incompatible", ToString()));
    }

    DateTime IConvertible.ToDateTime(IFormatProvider provider)
    {
      try
      {
        return new DateTime((this as IConvertible).ToInt64(provider));
      }
      catch (InvalidCastException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to DateTime because the values are incompatible", ToString()));
      }
    }

    decimal IConvertible.ToDecimal(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToInt32(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to Decimal because the values are incompatible", ToString()));
      }
    }

    double IConvertible.ToDouble(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToInt32(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to Double because the values are incompatible", ToString()));
      }
    }

    short IConvertible.ToInt16(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToInt16(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to Int16 because the values are incompatible", ToString()));
      }
    }

    int IConvertible.ToInt32(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToInt32(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to Int32 because the values are incompatible", ToString()));
      }

    }

    long IConvertible.ToInt64(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToInt64(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to Int64 because the values are incompatible", ToString()));
      }
    }

    sbyte IConvertible.ToSByte(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToSByte(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to sbyte because the values are incompatible", ToString()));
      }
    }

    float IConvertible.ToSingle(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToSingle(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to float because the values are incompatible", ToString()));
      }
    }

    string IConvertible.ToString(IFormatProvider provider)
    {
      return ToString();
    }

    object IConvertible.ToType(Type conversionType, IFormatProvider provider)
    {
      return Convert.ChangeType(ToString(), conversionType);
    }

    ushort IConvertible.ToUInt16(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToUInt16(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to UInt16 because the values are incompatible", ToString()));
      }
    }

    uint IConvertible.ToUInt32(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToUInt32(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to UInt32 because the values are incompatible", ToString()));
      }
    }

    ulong IConvertible.ToUInt64(IFormatProvider provider)
    {
      try
      {
        checked
        {
          return Convert.ToUInt64(ToString());
        }
      }
      catch (System.OverflowException)
      {
        throw new InvalidCastException(String.Format("Cannot convert {0} to UInt64 because the values are incompatible", ToString()));
      }
    }

    #endregion

    #region IComparable<StdBigNumber> Members

    int IComparable<StdBigNumber>.CompareTo(StdBigNumber other)
    {
      if (ReferenceEquals(other  ,null)) throw new ArgumentNullException("other");
      if (other.IsNegative && !IsNegative) return 1;
      if (!other.IsNegative && IsNegative) return -1;
      int sign = 1;
      if (IsNegative)
        sign = -1;
      if (other.DigitCount > DigitCount)
        return -sign;
      if (other.DigitCount < DigitCount)
        return sign;
      for (int i = DigitCount - 1; i >= 0; i--)
      {
        int myDigit = GetDigit(i);
        int otherDigit = other.GetDigit(i);
        if (myDigit != otherDigit)
          return (myDigit - otherDigit) * sign;
      }

      return 0;
    }

    public int CompareTo(StdBigNumber other)
    {
      if (ReferenceEquals(other  ,null)) throw new ArgumentNullException("other");
      return (this as IComparable<StdBigNumber>).CompareTo(other);
    }
    #endregion

    #region IBigNumber Members
    
    public IBigNumber IAdd(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      StdBigNumber sSecond = second as StdBigNumber;
      return this + sSecond;
    }

    public IBigNumber ISub(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      StdBigNumber sSecond = second as StdBigNumber;
      return this - sSecond;
    }

    public IBigNumber IMul(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      StdBigNumber sSecond = second as StdBigNumber;
      return this * sSecond;
    }

    public IBigNumber IDiv(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      StdBigNumber sSecond = second as StdBigNumber;
      return this / sSecond;
    }

    public IBigNumber IMod(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      StdBigNumber sSecond = second as StdBigNumber;
      return this % sSecond;
    }

    public IBigNumber IClone()
    {
      return new StdBigNumber(this);
    }

    public IBigNumber IConstruct(string number)
    {
      return new StdBigNumber(number);
    }

    public void IAbs()
    {
      IsNegative = false;
    }

    public bool IEqual(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      return this == (second as StdBigNumber);
    }

    public bool ISmaller(IBigNumber second)
    {
      if (ReferenceEquals(second  ,null)) throw new ArgumentNullException("second");
      return this < (second as StdBigNumber);
    }
    #endregion
  }
}
